//1.中序遍历+数组存储
class Solution {
public:
    vector<int> ret;
    TreeNode* MiddleTree(TreeNode* root) {
        if(root==nullptr) return nullptr;
        MiddleTree(root->left);
        ret.push_back(root->val);
        MiddleTree(root->right);

        return root;
    }

    bool isValidBST(TreeNode* root) {
        MiddleTree(root);
        for(int i=1; i<ret.size();++i) {
            if(ret[i] <= ret[i-1])
                return false;
        }
        return true;
    }
};
//2.递归判断区间
class Solution {
public:
    bool helper(TreeNode* root, long long lower, long long upper) {
        if (root == nullptr) {
            return true;
        }
        if (root -> val <= lower || root -> val >= upper) {
            return false;
        }
        return helper(root -> left, lower, root -> val) && helper(root -> right, root -> val, upper);
    }
    bool isValidBST(TreeNode* root) {
        return helper(root, (long long)INT_MIN-1, (long long)INT_MAX+1);
    }
};


//3.栈实现中序遍历
//栈实现中序遍历的过程中，存储前个节点的值，稍作修改
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> stack;
        long long inorder = (long long)INT_MIN - 1;

        while (!stack.empty() || root != nullptr) {
            while (root != nullptr) {
                stack.push(root);
                root = root -> left;
            }
            root = stack.top();
            stack.pop();
            // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if (root -> val <= inorder) {
                return false;
            }
            inorder = root -> val;
            root = root -> right;
        }
        return true;
    }
};
